def getNext(t):
    j=0
    k=-1
    next=[-1]
    while j<(len(t)-1):
        if k==-1 or t[j]==t[k]:
            j=j+1
            k=k+1
            next.append(k)
        else:
            k=next[k]
    return next

def kmpIndex(s,t):
    i=0
    j=0
    next=getNext(t)
    #print("s===",s,",t===",t)
    while i<len(s) and j<len(t):
        if j==-1 or s[i]==t[j]:
            i=i+1
            j=j+1
        else:
            j=next[j]
    if j>=len(t):
        return i-len(t)
    else:
        return -1
print(kmpIndex("abaabaabacacaabaabcc","abaabc"))
print(kmpIndex("aaaaab","aaab"))

# print(getNext('aaabbaab'))


        
